package com.atwy.sort;

/**
 * 快速排序
 * 一种分而治之思想在排序算法上的典型应用。
 * 本质上来看，快速排序应该算是在冒泡排序基础上的递归分治法。
 * 快速排序的基本思想：通过一趟排序将待排记录分隔成独立的两部分，
 * 其中一部分记录的关键字均比另一部分的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序。
 * <p>
 * 算法步骤:
 * 1.从数列中挑出一个元素，称为 "基准"（pivot）;
 * 2.重新排序数列，所有元素比基准值小的摆放在基准前面，
 * 所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。
 * 在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区（partition）操作；
 * <p>
 * 3.递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序；
 */
public class QuickSorting {

    public static void main(String[] args) {

        int[] array = {3, 65, 2, 34, 12, 5, 9, 12};
        sort(array);
        for (int i = 0; i < array.length; i++) {
            System.out.print(array[i] + "\t");
        }
        System.out.println();
        System.out.println("=============");

        /*int max = 80000;
        int arry[] = new int[max];
        for (int i = 0; i < max; i++) {
            arry[i] = (int)(Math.random()*8000000);
        }
        long start = System.currentTimeMillis();
        System.out.println("排序开始:"+start);
        sort(arry);
        long end = System.currentTimeMillis();
        System.out.println("排序结束:"+end);
        System.out.println("总耗时"+(end-start));*/

    }

    public static void sort(int[] arry) {
        quickSort(arry, 0, arry.length - 1);
    }

    /**
     * 看看这里的框架 和二叉树的前序遍历是不是一样的，
     *
     * 快速排序是先将一个元素排好序，然后再将剩下的元素排好序。
     *
     * partition 函数干的事情，其实就是把 nums[p] 这个元素排好序了。
     * @param arry
     * @param start
     * @param end
     */
    public static void quickSort(int[] arry, int start, int end) {
        // 递归结束条件
        if (start >= end) {
            return;
        }

        // 先分区，找到基准点
        int partition = partition(arry, start, end);
        // 分区进行递归
        quickSort(arry, start, partition - 1);
        quickSort(arry, partition + 1, end);

    }

    private static int partition(int[] arry, int start, int end) {
        // 假设基准
        int pivot = start;
        int base = arry[pivot];
        // 保证左边的小于基准，右边的大于基准
        while (start < end) {

            // 从右向左找，比基准小的下标
            while (start < end && arry[end] >= base) {
                end--;
            }
            // 从左往右找，比基准大的下标
            while (start < end && arry[start] <= base) {
                start++;
            }

            if(start < end){
                // 此时进行左右交换
                swap(arry,start,end);
                //交换之后，end下标已确定>=基准值，可跳过
                end--;
                // start 不调整，此时start指向小于基准值
                //start下标也确定<=基准值，但不能跳过，
                // 它可能是要与基准进行替换的值，也即是基准位置，如果++就是错误的位置了
                //而且循环的最外层是先判断从右往左的,即先进行end的判断
            }
        }
        // 将基准pivot放到相对中间位置
        swap(arry,pivot,start);
        return start;
    }

    private static void swap(int[] arry, int i, int j) {
        int temp = arry[i];
        arry[i] = arry[j];
        arry[j] = temp;
    }
}
